// https://www.lintcode.com/problem/find-all-anagrams-in-a-string/description
// 647. Find All Anagrams in a String
// 给定一个字符串 s 和一个 非空字符串 p ，找到在 s 中所有关于 p 的字谜的起始索引。
// 字符串仅由小写英文字母组成，字符串 s 和 p 的长度不得大于 40,000。
// 输出顺序无关紧要。

// 样例
// 给出字符串 s = "cbaebabacd" p = "abc"
// 返回 [0, 6]

// 子串起始索引 index = 0 是 "cba"，是"abc"的字谜.
// 子串起始索引 index = 6 是 "bac"，是"abc"的字谜.



class Solution {
public:
    /**
     * @param s: a string
     * @param p: a string
     * @return: a list of index
     */
    // // Time Limit Exceeded
    // // bool isAnagrams(string &s, string &t)
    // bool isAnagrams(string s, string t) //子串无法传引用？
    // {
    //     string s_tmp = s;
    //     string t_tmp = t;
    //     sort(s_tmp.begin(), s_tmp.end());
    //     sort(t_tmp.begin(), t_tmp.end());
    //     return s_tmp == t_tmp;
    // }
    // vector<int> findAnagrams(string &s, string &p) {
    //     // write your code here
    //     vector<int> result;
    //     // 输入"" "a"
    //     // 期望答案
    //     // []
    //     // Runtime Error
    //     if (s.empty())
    //     {
    //         return result;
    //     }
    //     // Time Limit Exceeded
    //     for (int i = 0; i <= (s.length() - p.length()); i++)
    //     {
    //         if (isAnagrams(s.substr(i, p.length()), p))
    //         {
    //             result.push_back(i);
    //         }
    //     }
    //     return result;
    // }
    
//     基本的想法：
// – 假设p串的长度为l , s串长度为n
// – 那么就枚举出s中所有长度为l 的子串，并用hash统计它们元素出现的个数
// • 基本想法的时间复杂度：
// – n个子串
// • 每次统计子串中元素出现的个数O(l)
// • 每次和p对比元素出现次数是否一样 O(256)
// – 总体O( n * (l + 256)) = O(nl)
   

//     法二：   
//   • 相当于一个长度为l 的sliding window 从左往右扫一遍
// – 每次都是右边增加一个，左边减少一个 O(l) → O(1)
// 时间复杂度：
// O(n * 256) = O(n)
// • 为什么有256这个常数项？可以优化吗？（扩展）
// – 怎样快速的判断下面的两个数组是否相等？ (cntS == cntP ?)
// • 定义det = cntS – cntP
// – 如果det全为0 → cntS == cntP
// • 怎样判断det全为0？
// – 所有的元素绝对值求和 absSum == 0 → det全为0
// • absSum 怎么更新？
// – 在sliding window向右移动时，减去原有的，加上改变的 O(1)
// 总体时间复杂度：O(n)
    // vector<int> findAnagrams(string &s, string &p) 
    // {
    //     vector<int> result;
    //     int l = p.length();
    //     char record[256] = {0};
    //     int sum = 0;
    //     if (s.empty())
    //     {
    //         return result;
    //     }
    //     for (int i = 0; i < l; i++)
    //     {
    //         record[p[i]]++;     
    //         record[s[i]]--;        
    //     }
    //     for (int i = 0; i < 256; i++)
    //     {
    //         sum += abs(record[i]);
    //     }
    //     for (int i = 0; i <= s.length() - p.length(); i++)
    //     {
    //         if (sum == 0)
    //         {
    //             result.push_back(i);
    //         }
    //         sum = sum - abs(record[s[i]]) - abs(record[s[i + l]]);
    //         record[s[i]]++;
    //         record[s[i + l]]--;
    //         // sum更新：减去原有的，加上更新的
    //         sum = sum + abs(record[s[i]]) + abs(record[s[i + l]]);
    //     }
    //     return result;
    // }
    
    // 法三：用matched来计数
     vector<int> findAnagrams(string& s, string& p) {
        // Write your code here
        vector<int> ans;
        int sum[30] = {0};
        ans.clear();
        int plength = p.length(), slength = s.length();
        for(int i = 0; i < plength; i ++){
            sum[p[i] - 'a'] ++;
        }
        
        int start = 0, end = 0, matched = 0;
        while(end < slength){
            if(sum[s[end] - 'a'] >= 1){
                matched ++;
            }
            sum[s[end] - 'a'] --;
            end ++;
            if(matched == plength) {
                ans.push_back(start);
            }
            if(end - start == plength){
                if(sum[s[start] - 'a'] >= 0){
                    matched --;
                }
                sum[s[start] - 'a'] ++;
                start ++;
            }
        }
        return ans;
    }
};